1422C - Bargain - CodeForces Solution


combinatorics dp math *1700

Please click on ads to support us..

Python Code:

import gc
import heapq
import itertools
import math
import sqlite3
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *
from fractions import Fraction


def S():
    return sys.stdin.readline().split()


def I():
    return [int(i) for i in sys.stdin.readline().split()]


def II():
    return int(sys.stdin.readline())


def IS():
    return sys.stdin.readline().replace('\n', '')


def is_prime(n):
    for i in range(2, int(n ** 0.5) + 2):
        if n % i == 0 and i < n:
            return False
    return True


def main():
    n = IS()
    _len = len(n)
    c = [(_len * (_len - 1) // 2) % mod, 0]
    tan = 1
    ans = 0
    for i in range(_len - 1, -1, -1):
        ans = (ans + (c[0] * pow(10, (_len - i - 1), mod) + c[1]) * int(n[i])) % mod
        c[0] = (c[0] - i) % mod
        c[1] = (c[1] + tan * (_len - i)) % mod
        tan = (tan * 10) % mod

    print(ans % mod)



if __name__ == '__main__':
    mod = 10 ** 9 + 7
            main()

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)1e18
#define pi (3.141592653589)
ll mod=1000000007;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
vector<ll>adj[200002];
vector<ll>vis(200002,0);
vector<ll>dis(200002,0);
#define countbit(a) __builtin_popcount(a)
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}  //for prime b
//void google(int t) {cout << Case # << t << : ;}
#define all(v) v.begin(),v.end()
/*returns nCr*/ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
#define vll vector<ll>
#define pll pair<ll,ll>
#define dec(n) cout<<fixed; cout<<setprecision(n);
ll dp1[1030][1020];
ll C(int n, int r){ if (r == 0 || r == n) return 1; if (dp1[n][r]) return dp1[n][r];return dp1[n][r] = (C(n - 1, r - 1) + C(n - 1, r)) % mod;}
/*ll up[200002][20];
ll depth[200002];
ll LCA(ll x,ll y){if(depth[x]>depth[y]) swap(x,y); ll d= depth[y]-depth[x];  for(int i=19;i>=0;i--){ if(d&(1<<i)) {y=up[y][i];}}if(x==y) return x; for(int i=19;i>=0;i--) {if(up[x][i]!=up[y][i]){x=up[x][i];y=up[y][i];}}return up[x][0];}
void LCAprec(ll node){vis[node]=1;for(auto x:adj[node]){if(vis[x]==0){depth[x]=depth[node]+1;up[x][0]=node;for(int i=1;i<20;i++){up[x][i]=up[up[x][i-1]][i-1];}LCAprec(x);}}}
*/

int main()
{
fast
int t=1;
//cin>>t;
for(int tc=1;tc<=t;tc++)
{
    string s;
    cin>>s;
    ll n=s.size();
    ll cur=0;
    ll ans=0;
    vector<ll>dp(n+1,1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=(expo(10,i,mod)+dp[i-1])%mod;
    }
    for(int i=0;i<n;i++)
    {
        cur=(10*cur+(s[i]-'0'))%mod;
        ll d=n-i-1;
        if(d-1>=0)
        ans+=(cur*dp[d-1])%mod;
        //cout<<ans<<" ";
        ans%=mod;
    }
    cur=0;
    for(int i=n-1;i>=1;i--)
    {
        cur=cur+(s[i]-'0')*expo(10,n-i-1,mod);
        cur%=mod;
        ans+=(cur*(i))%mod;
        ans%=mod;
    }
    cout<<ans<<'\n';
}


}


Comments

Submit
0 Comments
More Questions

97. Interleaving String
543. Diameter of Binary Tree
124. Binary Tree Maximum Path Sum
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
501A - Contest
160A- Twins
752. Open the Lock
1535A - Fair Playoff
1538F - Interesting Function
1920. Build Array from Permutation
494. Target Sum
797. All Paths From Source to Target
1547B - Alphabetical Strings
1550A - Find The Array
118B - Present from Lena
27A - Next Test
785. Is Graph Bipartite
90. Subsets II
1560A - Dislike of Threes
36. Valid Sudoku
557. Reverse Words in a String III
566. Reshape the Matrix
167. Two Sum II - Input array is sorted
387. First Unique Character in a String
383. Ransom Note
242. Valid Anagram
141. Linked List Cycle
21. Merge Two Sorted Lists
203. Remove Linked List Elements
733. Flood Fill